package com.yoshino.leetcode.interview150.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 将非递减数组合并到 nums1 中
        if (n == 0) {
            return;
        }
        if (m == 0) {
            System.arraycopy(nums2, 0, nums1, 0, n);
            return;
        }
        // 从后往前，越大放最后
        int ind = m + n - 1;
        m--;
        n--;
        while (m >= 0 && n >= 0) {
            if (nums1[m] > nums2[n]) {
                nums1[ind] = nums1[m--];
            } else {
                nums1[ind] = nums2[n--];
            }
            ind--;
        }
        while (m >= 0) {
            // 还有剩下
            nums1[ind--] = nums1[m--];
        }
        while (n >= 0) {
            nums1[ind--] = nums2[n--];
        }
    }

    public int removeElement(int[] nums, int val) {
        if (nums.length == 0) {
            return 0;
        }
        int ind = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[ind++] = nums[i];
            }
        }
        return ind;
    }

    public int removeDuplicates1(int[] nums) {
        // 删除重复元素
        int ind = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[ind++] = nums[i];
            }
        }
        return ind;
    }

    public int removeDuplicates(int[] nums) {
        // 保留仅出现不超过2次
        if (nums.length < 3) {
            return 2;
        }
        int ind = 2;
        for (int i = 2; i < nums.length; i++) {
            // 存储完成的是否重复的
            if (nums[i] != nums[i - 1] || nums[ind - 1] != nums[ind - 2]) {
                nums[ind++] = nums[i];
            }
        }
        return ind;
    }

    public int majorityElement(int[] nums) {
        // 使用计数器法，剩下的对应的数 一定是多数元素
        int res = nums[0], count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (res != nums[i]) {
                count--;
                if (count < 0) {
                    count = 1;
                    res = nums[i];
                }
            } else {
                count++;
            }
        }
        return res;
    }

    public void rotate(int[] nums, int k) {
        // 翻转数组：1234567 k=3
        // 7654321 -> 567 4321 -> 567 1234
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        int temp;
        while (start < end) {
            temp = nums[end];
            nums[end] = nums[start];
            nums[start] = temp;
            start++;
            end--;
        }
    }

    public int maxProfit1(int[] prices) {
        // 保留当前遍历过的最小值
        int min = prices[0], res = 0;
        for (int i = 1; i < prices.length; i++) {
            if (min < prices[i]) {
                res = Math.max(res, prices[i] - min);
            } else {
                min = prices[i];
            }
        }
        return res;
    }

    public int maxProfit(int[] prices) {
        // 只要有递增就加入
        // 1 3 6
        int min = prices[0], res = 0;
        for (int i = 1; i < prices.length; i++) {
            if (min < prices[i]) {
                res += prices[i] - min;
            }
            min = prices[i];
        }
        return res;
    }

    public boolean canJump(int[] nums) {
        // 贪心
        // 对于该点 i，最大收益为 在 0 - i 中可以跳的最远距离
        boolean flag = false;
        if (nums.length < 2) {
            return true;
        }
        int maxDis = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (i <= maxDis) {
                // 可达该点
                maxDis = Math.max(maxDis, nums[i] + i);
            } else {
                break;
            }
        }
        return maxDis >= nums.length - 1;
    }

    public int jump(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int step = 0;
        int nextReach = nums[0], reach = nextReach;
        for (int i = 0; i < nums.length; i++) {
            // 1 3 4
            nextReach = Math.max(nextReach, nums[i] + i);
            if (nextReach >= nums.length - 1) {
                return step + 1;
            }
            if (i == reach) {
                // 到达上一个点的最远点
                reach = nextReach;
                step++;
            }
        }
        return step;
    }

    public int hIndex2(int[] citations) {
        // 排序，从后往前比较
        // 1 2 3 4     2
        Arrays.sort(citations);
        int res = 1;
        for (int i = citations.length - 1; i >= 0; i--) {
            if (citations[i] >= res) {
                res++;
            } else {
                break;
            }
        }
        return res - 1;
    }

    public int hIndex(int[] citations) {
        // 计数法
        int n = citations.length;
        int[] counter = new int[n + 1];
        for (int i = 0; i < n; i++) {
            if (citations[i] >= n) {
                counter[n]++;
            } else {
                counter[citations[i]]++;
            }
        }
        int tot = 0;
        for (int i = n; i >= 0; i--) {
            tot += counter[i];
            if (tot >= i) {
                return i;
            }
        }
        return 0;
    }

    public int[] productExceptSelf(int[] nums) {
        // 左右两边乘积 相乘
        int n = nums.length;
        int[] left = new int[n], right = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }

        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }
        for (int i = 0; i < n; i++) {
            nums[i] = right[i] * left[i];
        }
        return nums;
    }

    public int canCompleteCircuit(int[] gas, int[] cost) {
        // 该点 的输出 - 存储 < 0 不能作为起始
        // 累计的 输出 - 存储 < 0 不能作为起始
        int cur = 0, tot = 0, begin = 0;
        for (int i = 0; i < gas.length; i++) {
            cur += gas[i] - cost[i];
            tot += gas[i] - cost[i];
            if (cur < 0) {
                cur = 0;
                begin = i + 1;
            }
        }
        return tot >= 0? begin : -1;
    }

    public int candy(int[] ratings) {
        // 先只看左边
        int length = ratings.length;
        int[] candy = new int[length];
        candy[0] = 1;
        for (int i = 1; i < length; i++) {
            candy[i] = (ratings[i] > ratings[i - 1]) ? candy[i - 1] + 1 : 1;
        }
        for (int i = length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candy[i] = Math.max(candy[i], candy[i + 1] + 1);
            }
        }
        int res = 0;
        for (int i : candy) {
            res += i;
        }
        return res;
    }

    public int trap(int[] height) {
        // 使用累高，左右两边累高
        int n = height.length, res = 0;
        int[] left = new int[n], right = new int[n];
        // 从左边开始
        left[0] = height[0];
        for (int i = 1; i < n; i++) {
            left[i] = Math.max(height[i], left[i - 1]);
        }
        // 从右边开始
        right[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], height[i]);
        }
        for (int i = 0; i < n; i++) {
            res += Math.min(right[i], left[i]) - height[i];
        }
        return res;
    }

    public int romanToInt(String s) {
        int sum = 0;
        int preNum = getValue(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            int num = getValue(s.charAt(i));
            if (preNum < num) {
                sum -= preNum;
            } else {
                sum += preNum;
            }
            preNum = num;
        }
        sum += preNum;
        return sum;
    }

    private int getValue(char ch) {
        switch(ch) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    }

    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < values.length; i++) {
            int val = values[i];
            String sym = symbols[i];
            while (num >= val) {
                num -= val;
                sb.append(sym);
            }
            if (num == 0) {
                break;
            }
        }
        return sb.toString();
    }

    public int lengthOfLastWord(String s) {
        int res = 0, ind = s.length() - 1;
        while (s.charAt(ind) == ' ') {
            ind--;
        }
        while (ind >= 0 && s.charAt(ind) != ' ') {
            res++;
            ind--;
        }
        return res;
    }

    public String longestCommonPrefix(String[] strs) {
        int n = strs.length, min = strs[0].length(), cur = 0;
        for (int i = 1; i < n; i++) {
            min = Math.min(min, strs[i].length());
        }
        while (cur < min) {
            char tmp = strs[0].charAt(cur);
            for (int i = 1; i < n; i++) {
                if (tmp != strs[i].charAt(cur)) {
                    return strs[i].substring(0, cur);
                }
            }
            cur++;
        }
        return strs[0].substring(0, cur);
    }

    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        String[] split = s.trim().split(" +");
        for (int i = split.length - 1; i > 0; i--) {
            sb.append(split[i]).append(' ');
        }
        sb.append(split[0]);
        return sb.toString();
    }

    public String convert(String s, int numRows) {
        if (numRows < 2) {
            return s;
        }
        List<StringBuilder> rows = new ArrayList<>(numRows);
        for (int i = 0; i < numRows; i++) {
            rows.add(new StringBuilder());
        }
        int ind = 0, flag = -1;
        for (char c : s.toCharArray()) {
            rows.get(ind).append(c);
            if (ind == 0 || ind == numRows - 1) {
                flag *= -1;
            }
            ind += flag;
        }
        StringBuilder res = new StringBuilder();
        for (StringBuilder row : rows) {
            res.append(row);
        }
        return res.toString();
    }

    public int strStr2(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

    public int strStr(String haystack, String needle) {
        if (needle.length() > haystack.length()) {
            return -1;
        }
        for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
            if (haystack.charAt(i) == needle.charAt(0)) {
                int temp = i + 1;
                boolean flag = true;
                for (int j = 1; j < needle.length(); j++) {
                    if (haystack.charAt(temp++) != needle.charAt(j)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    return i;
                }
            }
        }
        return -1;
    }

    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        int right = 0, n = words.length;
        while (true) {
            int left = right;
            int sumLen = 0;
            while (right < n && sumLen + words[right].length() + right - left <= maxWidth) {
                sumLen += words[right++].length();
            }
            if (right == n) {
                // 最后一行
                StringBuilder sb = join(words, left, n, " ");
                sb.append(blank(maxWidth - sb.length()));
                res.add(sb.toString());
                return res;
            }

            int wordNum = right - left;
            int spacesNum = maxWidth - sumLen;

            if (wordNum == 1) {
                // 只有一个单词
                StringBuilder sb = new StringBuilder(words[left]);
                sb.append(blank(spacesNum));
                res.add(sb.toString());
                continue;
            }
            int avgSpaces = spacesNum / (wordNum - 1);
            int extraSpa = spacesNum % (wordNum - 1);
            StringBuilder sb = new StringBuilder();
            sb.append(join(words, left, left + extraSpa + 1, blank(avgSpaces + 1)));
            sb.append(blank(avgSpaces));
            sb.append(join(words, left + extraSpa + 1, right, blank(avgSpaces)));
            res.add(sb.toString());
        }
    }

    private String blank(int n) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            stringBuilder.append(' ');
        }
        return stringBuilder.toString();
    }

    private StringBuilder join(String[] words, int left, int right, String sep) {
        StringBuilder sb = new StringBuilder(words[left]);
        for (int i = left + 1; i < right; i++) {
            sb.append(sep);
            sb.append(words[i]);
        }
        return sb;
    }


    public static void main(String[] args) {
        System.out.println(new Solution().removeDuplicates(new int[]{1, 1, 1, 2, 2, 3}));
    }
}